#include<iostream>

#include<vector>
using namespace std;


int Solutionnums;

void dfs(int path, int target, int level, vector<int>& nums, int pos)
{
    if (path == target && level == nums.size())
    {
        Solutionnums++;
        return;
    }

    for (int i = pos; i < nums.size(); i++)
    {
        path += nums[i];
        dfs(path, target, level + 1, nums, i + 1);
        path -= nums[i];
        dfs(path, target, level + 1, nums, i + 1);
    }
}

int findTargetSumWays(vector<int>& nums, int target)
{
    dfs(0, target, 0, nums, 0);
    return Solutionnums;
}




int main()
{
    vector<int> nums = { 1,1,1,1,1 };
    findTargetSumWays(nums, 3);
    return 0;
}

class Solution {
public:
    int sum;
    int aim;
    int findTargetSumWays(vector<int>& nums, int target) {
        aim = target;
        dfs(nums, 0, 0);
        return sum;
    }

    void dfs(vector<int>& nums, int path, int level)
    {
        if (level == nums.size())
        {
            if (aim == path) sum++;
            return;
        }

        dfs(nums, path + nums[level], level + 1);

        dfs(nums, path - nums[level], level + 1);
    }
};
